/*
 * @lc app=leetcode.cn id=146 lang=typescript
 *
 * [146] LRU 缓存机制
 */

// @lc code=start

//  思想：哈希双向链表
//  参考：https://labuladong.github.io/algo/2/18/38/
class LRUCache {
    map: Map<number, LinkNode>
    cache: DoubleList
    cap: number // 最大容量
    constructor(capacity: number) {
        this.cap = capacity
        this.map = new Map()
        this.cache = new DoubleList()
    }
    // 获取数据
    get(key: number): number {
        if (!this.map.has(key)) return -1
        // 将该数据提升为最近使用的
        this.makeRecently(key)
        return this.map.get(key)!.val
    }
    // 添加数据
    put(key: number, value: number): void {
        if (this.map.has(key)) {
            this.deleteKey(key)
            this.addRecently(key, value)
            return
        }
        if (this.cap === this.cache.size) {
            // 删除最久未使用的元素
            this.removeLeastRecently()
        }
        // 添加为最近使用的元素
        this.addRecently(key, value)
    }
    // 将某个 key 提升为最近使用的
    makeRecently(key: number) {
        const x = this.map.get(key)
        // 先从链表中删除这个节点
        this.cache.remove(x!)
        // 重新插到队尾
        this.cache.addLast(x!)
    }
    // 添加最近使用的元素
    addRecently(key: number, val: number) {
        const x = new LinkNode(key, val)
        // 链表尾部就是最近使用的元素
        this.cache.addLast(x)
        // 别忘了在 map 中添加 key 的映射
        this.map.set(key, x)
    }
    // 删除某一个 key
    deleteKey(key: number) {
        const x = this.map.get(key)
        this.cache.remove(x!)
        this.map.delete(key)
    }
    // 删除最久未使用的元素
    removeLeastRecently() {
        // 链表头部的第一个元素就是最久未使用的
        const deletedNode = this.cache.removeFirst()
        const deletedKey = deletedNode!.key
        this.map.delete(deletedKey)
    }
}
class LinkNode {
    key: number
    val: number
    prev: LinkNode | null
    next: LinkNode | null
    constructor(key: number, val: number) {
        this.key = key
        this.val = val
        this.prev = null
        this.next = null
    }
}
class DoubleList {
    head: LinkNode
    tail: LinkNode
    size: number
    constructor() {
        this.head = new LinkNode(0, 0)
        this.tail = new LinkNode(0, 0)
        this.head.next = this.tail
        this.tail.prev = this.head
        this.size = 0
    }
    // 在链表尾部添加节点 x
    addLast(x: LinkNode) {
        x.prev = this.tail.prev
        x.next = this.tail
        this.tail.prev!.next = x
        this.tail.prev = x
        this.size++
    }
    // 删除链表中的 x 节点
    remove(x: LinkNode) {
        x.prev!.next = x.next
        x.next!.prev = x.prev
        this.size--
    }
    // 删除链表中第一个节点，并返回该节点
    removeFirst(): LinkNode | null {
        if (this.head.next === this.tail) return null
        const first = this.head.next
        this.remove(first!)
        return first
    }
}
/**
 * Your LRUCache object will be instantiated and called as such:
 * var obj = new LRUCache(capacity)
 * var param_1 = obj.get(key)
 * obj.put(key,value)
 */
// @lc code=end

const lRUCache = new LRUCache(2)
lRUCache.put(1, 1) // 缓存是 {1=1}
lRUCache.put(2, 2) // 缓存是 {1=1, 2=2}
lRUCache.get(1)    // 返回 1
lRUCache.put(3, 3) // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2)    // 返回 -1 (未找到)
lRUCache.put(4, 4) // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1)    // 返回 -1 (未找到)
lRUCache.get(3)    // 返回 3
lRUCache.get(4)    // 返回 4